#pragma once
#include <iostream>
#include "../utils/Array.h"

//指向排序算法的函数指针
typedef void(*P_SortFn)(int*, int);
using namespace std;
using namespace csz;

class SortFamily {
public:
	/// 构造函数
	SortFamily() {
	}
	/* 调用函数指针指向的排序方法 */
	void MySort(P_SortFn sortFn, int* arr, int len) {
		(*sortFn)(arr, len);
	}
	/* 冒泡排序 */
	void BubbleSort(int* arr, int len) {
		int i, j;
		if (arr == NULL || len <= 0) {
			return;
		}
		for (i = 0; i < len; i++) {
			for (j = 0; j < len - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					Array<int>::Swap(&arr[j], &arr[j + 1]);
				}
			}
		}
	}
	/* 选择排序 */
	void SelSort(int* arr, int len) {
		int i, j, min;
		for (i = 0; i < len; i++) {
			min = i;
			for (j = i + 1; j < len; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			Array<int>::Swap(&arr[i], &arr[min]);
		}
	}
	/* 插入排序 */
	void InsSort(int* arr, int len) {
		int i, j, x;
		for (i = 1; i < len; i++) {
			if (arr[i] < arr[i - 1]) {
				x = arr[i];
				j = i - 1;
				while (x < arr[j] && j >= 0) {
					arr[j + 1] = arr[j];
					j--;
				}
				arr[j + 1] = x;
			}
		}
	}
	/* 希尔排序，本质上是对插入排序的一种改进（在外面包了一层递减的增量h）*/
	void ShellSort(int* arr, int len) {
		int h = 0, i, j, x;
		while (h <= len) {
			h = 3 * h + 1;
		}
		while (h > 0) {
			for (i = h; i < len; i++) {
				if (arr[i] < arr[i - h]) {
					x = arr[i];
					j = i - h;
					while (j >= 0 && x < arr[j]) {
						arr[j + h] = arr[j];
						j -= h;
					}
					arr[j + h] = x;
				}
			}
			h = (h - 1) / 3;
		}
	}
	/* 堆排序 */
	void HeapSort(int* arr, int len) {
		int i;
		for (i = len / 2 - 1; i >= 0; i--) {//建立初始堆
			HeapAdjust(arr, len, i);
		}
		for (i = len - 1; i > 0; i--) {//将最后一个元素和第一个元素交换并再次调整堆
			Array<int>::Swap(&arr[0], &arr[i]);
			HeapAdjust(arr, i, 0);
		}
	}
	/* 堆调整（调整为最大堆，对应升序排序）*/
	void HeapAdjust(int* arr, int len, int i) {
		int child;
		for (; 2 * i + 1 < len; i = child) {
			child = 2 * i + 1;//child为左子节点的位置
			if (child<len - 1 && arr[child + 1]>arr[child]) {
				child++;//右子节点大于左子节点，最大值为右子节点
			}
			if (arr[i] < arr[child]) {
				Array<int>::Swap(&arr[i], &arr[child]);//子节点大于父节点，将最大子节点与父节点交换
										   //为了避免调整后以子节点为父节点的二叉树不是堆，需要对该子节点所在的树进行再次调整
			}
			else {
				break;//父节点为最大节点，无需调整
			}
		}
	}
	/* 合并数组 */
	void MergeArr(int arr[], int first, int mid, int last, int tmp[]) {
		int i = first, j = mid + 1;
		int m = mid, n = last;
		int k = 0;
		while (i <= m && j <= n) {
			if (arr[i] < arr[j]) {
				tmp[k++] = arr[i++];
			}
			else {
				tmp[k++] = arr[j++];
			}
		}
		while (i <= m) {
			tmp[k++] = arr[i++];
		}
		while (j <= n) {
			tmp[k++] = arr[j++];
		}
		for (i = 0; i < k; i++) {
			arr[first + i] = tmp[i];
		}
	}
	/* 归并排序 */
	void MergeSort(int arr[], int start, int stop, int tmp[]) {
		int mid;
		if (start < stop) {
			mid = (start + stop) / 2;
			MergeSort(arr, start, mid, tmp);
			MergeSort(arr, mid + 1, stop, tmp);
			MergeArr(arr, start, mid, stop, tmp);
		}
	}
	/* 快速排序 */
	void QuickSort(int arr[], int left, int right) {
		int i = left, j = right;
		int tmp = arr[i];
		if (left >= right) {
			return;
		}
		while (i < j) {
			while (i < j && tmp <= arr[j]) {
				j--;
			}
			arr[i] = arr[j];
			while (i < j && tmp >= arr[i]) {
				i++;
			}
			arr[j] = arr[i];
		}
		arr[i] = tmp;
		QuickSort(arr, left, i - 1);
		QuickSort(arr, i + 1, right);
	}
	/* 基数排序 */
	/* 待补充 */
};